1. Field of the Invention
The present invention is related to the field of three-dimensional graphics rendering. Specifically, the present invention is related to the problem of calibrating the z-buffer granularity or depth based upon the objects in a scene.
2. Discussion of the Related Art
A Z-buffer is an area in graphics memory reserved for storing the Z-axis value of each pixel. Z-buffing is an algorithm used in 3-D graphics to determine which objects, or parts of objects, are visible and which are hidden behind other objects. With Z-buffering, the graphics processor stores the Z-axis value of each pixel in a special area of memory called the Z-buffer. Different objects can have the same x- and y-coordinate values, but with different z-coordinate values. The object with the lowest z-coordinate value is in front of the other objects, and therefore that""s the one that""s displayed.
3-D graphics is the field of computer graphics concerned with generating and displaying three-dimensional objects in a two-dimensional space (e.g., the display screen). Whereas pixels in a 2-dimensional graphic have the properties of position, color, and brightness, a 3-D pixels adds a depth property that indicates where the point lies on an imaginary Z-axis. When many 3-D pixels are combined, each with its own depth value, the result is a three-dimensional surface, called a texture. In addition to textures, 3-D graphics also supports multiple objects interacting with one another. For example, a solid object may partially hide an object behind it. Finally, sophisticated 3-D graphics use techniques such as ray tracing to apply realistic shadows to an image.
Converting information about 3-D objects into a bit map that can be displayed is known as rendering, and requires considerable memory and processing power. In the past, 3-D graphics was available only on powerful workstations, but now 3-D graphics accelerators are commonly found in personal computers. The graphics accelerator contains memory and a specialized microprocessor to handle many of the 3-D rendering operations.
One of the big challenges of translating 3D environments into rapidly changing 2D frames is fighting out what surfaces are hidden by other objects and should not be visible. Two techniques used to correctly position objects are called Z-sorting and Z-buffering. (The xe2x80x98Zxe2x80x99 is the Z-direction of depth.) The Z-sorting algorithm simply arranges polygons in back-to-front order before rendering, and draws the front polygons last. It produces correct results except when objects pass through other objects, in which case they appear as stacked instead of intersecting. Z-sorting is performed by the host CPU and involves considerable overhead which, naturally, translates into lower frame rates.
By contrast, Z-buffering can be effectively implemented in a hardware rendering engine, but at the expense of dedicating more memory to the job. A Z-buffer involves a block of memory equal to the display resolution (e.g. 640xc3x97480) multiplied by the number of bits of depth resolution desired (e.g. 16-bits). The Z-buffer algorithm stores a depth value for each pixel in the display. When rendering objects, the engine calculates a Z-value for each pixel and stores that value in the Z-buffer memory location corresponding to the X/Y address of the pixel in the display buffer. The lower the Z-value, the closer the object is to the viewer. When a new pixel is rendered its Z-value is compared with the Z-value of the current pixel and only if the Z-value of the new pixel is less than the one already stored will the new pixel be written to the display buffer.
When rendering 3D objects to the screen, often a z-buffer is used to sort the objects. If the z-buffer is not deep enough, or if it is too finely grained, then two objects will be sorted into the same z-buffer slot. This produces visible anomalies (shimmering) when rendering. To remedy this, developers adjust the z-buffer to be deeper or to be more finely grained based on the situation. However, when the z-buffer is calibrated based upon the objects in a changing scene, the changes in the scene may result in undesirable visual discontinuities as the z-buffer calibration results in different z-buffer depths during each frame, thereby changing the position of each object within the z-buffer from frame to frame.
When rendering 3D objects to the 2D display, a common technique is to sort the objects into a z-buffer. The rendering engine sorts the objects along the z-dimension (into the screen). The z-buffer represents a fixed amount of memory into which the objects are sorted.
Either that memory can represent a large distance (depth) or it can be fine-grained for better resolution when objects are close to one another. For example, when rendering a 3D object representing a book, then the pages are close to one another and the z-buffer must be finely partitioned to keep the objects separate. But when two objects are far apart, such as two spheres representing planets, then the z-buffer must stretch over a large distance.
Programmers can adjust the granularity of the z-buffer based on what is in the scene. When they need high resolution and depth, they must decide what is the best value. For example, they may decide that objects closer to the center of the screen are more valuable to the user, and therefore have more influence on the adjustment of the z-buffer granularity. But if the object is constantly moving in and out of the center of the screen, then this z-buffer adjustment becomes more volatile.
As is apparent from the above discussion, a need exists for determining the weights associated with the objects in a scene for performing the z-buffer calibration before rendering each frame.
Programmers can adjust the granularity of the z-buffer based on what is in the scene. When they need high resolution and depth, they must decide what is the best value. For example, they may decide that objects closer to the center of the screen are more valuable to the user, and therefore have more influence on the adjustment of the z-buffer granularity. But if the object is constantly moving in and out of the center of the screen, then this z-buffer adjustment becomes more volatile. An object of the present invention is to provide a method for determining the weights associated with the objects in a scene for performing the z-buffer calibration before rendering each frame.
According to the present invention, the weight given to each object in a scene in the computation of the z-buffer granularity is determined based upon a variable risk parameter which may be supplied by the application. In the preferred embodiment, the risk parameter is normalized assuming values between zero and one, inclusive.
The leaf objects in the scene are preferably organized into a binary tree, whose structure may indicate the importance of the leaf objects. Composite parent objects each have two children objects. Children objects are either leaf objects or composite parent objects. Each composite parent object contains both of its children objects and all of the objects contained by both of its children object. The importance ranking of objects is optionally determined by one of a variety of methods. For example, the importance ranking may be predetermined based upon the type of object. Alternatively, the importance ranking is determined by decreasing order of mean hit values determined over a predetermined number of frames. As yet another alternative, the importance ranking of the objects in the scene is determined by the distances of the objects from the observation point. For example, the closest objects may be assigned the highest importance. Some combination of the above described methods for ranking the objects may also be performed in accordance with the present invention.
In a greedy algorithm embodiment, the most important object is a child of the scene object, and each composite parent object has as its two children one leaf object and one composite parent object except the deepest composition parent object which contains the least important two leaf objects. The leaf objects decrease in importance as their depth in the binary tree in this greedy embodiment.
However, the methods of the present invention are applicable to scene having any arbitrary binary tree structure. The scene object contains all leaf objects and has no parent. A recursive composite parent object process is invoked upon the two children of the scene object. In the recursive composite parent object process, graphics resources are allocated to objects A and B. A primary hit value mean corresponding to one of object A and object B is computed. In the preferred embodiment, the primary hit value mean is the average sum of hit values recorded for all the leaf objects contained by the object over a predetermined number of frames. Hit values are, for example, binary variables which take on a zero when the leaf object is not in a central portion of the scene during a frame and takes on a one if the leaf object is in the central portion of the scene during the frame. Alternatively, the hit value is a function of a static or dynamic importance weight associated with the leaf object.
According to an aspect of the present invention, the hit values for all objects contained by the other of object A and object B are summed for each of the previous predetermined number of frames to produce a secondary hit value for each of the frames. The secondary hit value mean is computed as the average of the sum of hit values for all objects contained by the other of object A and object B.
According to another aspect of the present invention, the statistical variances of the primary hit value and secondary hit value are also computed over the previous predetermined number of frames. The computation of the statistical variances of the primary and secondary hit values according to the present invention facilitates the mapping of the normalized risk parameter to a non-normalized risk parameter indicating the optimal risk for objects A and object B. The non-normalized risk parameter is substituted into a parametric variance equation. According to the present invention, the parametric variance equation is solved for the optimal fraction of the remaining graphics resources to be allocated to object A.
In the preferred embodiment, the parametric variance equation is a quadratic equation which omits a correlation term between the primary and secondary hit values. If the primary hit value mean is greater than or equal to the secondary hit value mean, the method selects the greater solution of the quadratic variance equation as the optimal fraction. Conversely, if the primary hit value mean is less than the secondary hit value mean, the method selects the lesser solution of the quadratic variance equation as the optimal fraction. The optimal fraction is multiplied by the available graphics resources, resulting in the resources allocated to object A. The available graphics resources which are not allocated to object A are allocated to object B.
According to an embodiment of the present invention, if object A is a composite parent object, the recursive parent object process is invoked on the two children of object A with the available graphics resources for the instantiation of the recursive parent object process set to the graphics resources allocated to object A. If object B is a composite parent object, the recursive parent object process is invoked on the two children of object B with the available graphics resources for the instantiation of the recursive parent object process set to the graphics resources allocated to object B. In this manner, the total graphics resources available at the scene object is recursively divided up amongst all of the scene""s leaf nodes.
According to an embodiment of the present invention, the resources allocated each object are then used as weighting factors in the computation of the z-buffer granularity. For example, in an embodiment, the z-buffer midpoint depth is determined by dividing the multiplicative product of the distance from the observation point and the allocated resources by the sum of the allocated resources for all objects. In another embodiment, the z-buffer midpoint depth is determined by dividing the sum of the multiplicative products of the distance from the observation point, the allocated resources, and the importance coefficient for each object by the sum of the products of the observation point and the allocated resources for each object.
According to another aspect of the present invention, the non-normalized risk parameter is computed by adding the normalized risk parameter times the difference between a maximum risk and minimum risk to the minimum risk. The maximum risk is the risk associated with hit value mean having the highest value.
These and other features, aspects, and advantages of the present invention are fully described in the Detailed Description of the Invention and the Figures.